import java.util.*;

public class Solution17 {

    private List<Character>[] getNumCharMap(){
        List<Character>[] numCharMap = new List[8];
        numCharMap[0] = Arrays.asList('a', 'b', 'c');
        numCharMap[1] = Arrays.asList('d', 'e', 'f');
        numCharMap[2] = Arrays.asList('g', 'h', 'i');
        numCharMap[3] = Arrays.asList('j', 'k', 'l');
        numCharMap[4] = Arrays.asList('m', 'n', 'o');
        numCharMap[5] = Arrays.asList('p', 'q', 'r', 's');
        numCharMap[6] = Arrays.asList('t', 'u', 'v');
        numCharMap[7] = Arrays.asList('w', 'x', 'y', 'z');
        return numCharMap;
    }

    public List<String> letterCombinations(String digits) {
        List<Character>[] numCharMap = getNumCharMap();
        List<String> res = new ArrayList<>();
        Queue<String> q = new LinkedList<>();
        q.add("");
        while(!q.isEmpty()){
            String tmpStr = q.poll();
            int tmpLen = tmpStr.length();
            if(tmpLen >= digits.length()){
                if(tmpLen > 0){
                    res.add(tmpStr);
                }
            }
            else {
                List<Character> charList = numCharMap[digits.charAt(tmpLen) - '2'];
                for (Character c : charList) {
                    q.add(tmpStr + c);
                }
            }
        }
        return res;
    }
}
